A pseudorandom string is one that, although produced deterministically, is impossible to distinguish, at least in a reasonable time, from a string of symbols in which each symbol is chosen entirely at random from the alphabet (the meaning of reasonable time is obviously linked to the target application and to the available computation power). In practice, a pseudorandom string is usually produced by initializing an appropriate algorithm using a secret parameter (called the seed or key, depending on the context), and where appropriate an additional parameter, secret or not, called the initialization vector.
The alphabet referred to above can be the binary set {0,1}, the set of digits from 0 to 9 or the alphanumeric set comprising those digits and the uppercase and lowercase letters. In the context of the present invention, the symbols of the alphabet belong to a finite body K or Galois body GF(q) of cardinal q≧2.
An important application of pseudorandom strings is stream encryption. This technique is used to encrypt (in the cryptographic sense) a string of data in clear {xi} (indexed by i) with values in the alphabet by means of another string {zi} of values in the same alphabet, where {zi} is a string produced by a pseudorandom generator, to produce an encrypted string {yi}, also with values in the alphabet. In other words, a law of internal composition yi=xi*zi within the alphabet is chosen; for example, this internal law can be the exclusive OR operator if the alphabet is the binary alphabet {0,1}. Stream encryption is also known as on the fly encryption because data words are encrypted one by one, as opposed to encryption methods operating on blocks of data. Compared to block encryption, stream encryption has the advantage of reducing transmission delay and data storage problems, but obviously requires a pseudorandom symbol data rate at least as high as the data rate of the data in clear; the application to stream encryption is therefore reserved to relatively fast pseudorandom string generators.
Stream encryption is used in the TLS (Transport Layer Security) Internet exchange protection protocol (see “The TLS Protocol”, T. Dierks and C. Allen, version 1.0, RFC 2246, January 1999), one of the most widely used stream encryption algorithms of which is the RC4 algorithm (see “Linear Statistical Weakness of Alleged RC4 Keystream Generator”, J. D. Golic, proceedings of “Advances in Cryptology—EUROCRYPT '97”, pages 226 to 238, editor W. Fumy, Lecture Notes in Computer Science vol. 1233, Springer-Verlag), and in radio channel traffic and signaling encryption in the GSM system using algorithms of which the most widely used is the A5/1 algorithm (see “Real Time Cryptanalysis of A5/1 on a PC”, A. Biryukov, A. Shamir, and D. Wagner, Proceedings of FSE 2000, pages 1 to 18, editor B. Schneier, Springer-Verlag 2000).
There are other important applications of pseudorandom strings, for example stochastic calculations and public key authentication cryptography protocols.
Many current stream algorithms, for example the A5/1 algorithm referred to above, use recurrent linear strings produced by linear feedback registers, possibly combined using non-linear functions (see “Le chiffrement à la volée” [“On the fly encryption”], A. Canteaut, special issue of the review “Pour la Science”, pages 86 and 87, Paris, July-October 2002). Those algorithms can be implemented in fast pseudorandom string generators but caution is called for with regard to their security, as they lack strong security arguments on which great confidence can be placed, concerning the impossibility in practice of distinguishing the pseudorandom strings produced from totally random strings.
French patent application 05 06041 discloses a generator of pseudorandom strings of terms belonging to a finite body K of cardinal q≧2 intended to be used in a cryptography procedure. This generator includes means for calculating iteratively, from an initialization n-tuple X(0)=(X(0)1, X(0)2, . . . , X(0)n) of elements of K, n-tuples X(i)=(X(i)1, X(i)2, . . . , X(i)n) of elements of K (where i=1, 2, . . . ), each n-tuple X(i) resulting in a predetermined manner from an m-tuple Y(i)=(Y(i)1, Y(i)2, . . . , Y(i)m) of elements of K and the terms of said pseudorandom string being extracted in a predetermined way from the n-tuples X(i) and/or the m-tuples Y(i). This generator is noteworthy in that it further includes means for obtaining, for one or more values of i, one or more components Y(i)k (where k=1, 2, . . . , m) of the m-tuple Y(i) by applying to the components of the n-tuple X(i−1) a predetermined quadratic form with coefficients in K.
This pseudorandom generator uses an algorithm offering a high level of security, given the difficulty of the problem of solving a system of quadratic equations over a finite body. Subject to verification of the commonly accepted conjecture P≠NP of complexity theory, it can be shown that, whatever the finite body K considered, solving this problem requires more than polynomial time, even if verifying whether a given candidate is or is not a solution of this system of equations can be effected in polynomial time (this kind of problem is called an NP-hard problem). Moreover, even for relatively modest sizes of m and n (for example for K=GF(2) and m and n greater than or equal to 100), if the values of m and n are sufficiently close, no efficacious method of solving random instances of this problem is known at present.
This being so, the question arises of determining whether a pseudorandom generator according to French patent application 05 06041 can be sufficiently effective, i.e. require computation resources (time, memory, etc.) for each symbol of the string produced that are sufficiently small (at least for moderate parameter values, but nevertheless sufficiently high for the problem just mentioned still to be considered difficult) for use of this kind of generator on the industrial scale to be envisaged.
This question of required calculation resources relates in particular to the possibility of integrating a pseudorandom generator of this type into low-cost electronic systems such as hardwired logic chips. Hardwired electronic logic circuits are made up of logic gates produced from transistors (it is possible to conceive of all the logic functions of a program using logic gates of two types, NAND gates and NOR gates). The number of logic gates required to implement a logic circuit therefore reflects in particular the size of the circuit, its current consumption, and its cost.
Consider therefore in more detail the calculations carried out in the pseudorandom generator of French patent application 05 06041.
The generator calls iteratively one or more quadratic form(s) associating, on iteration i, at least one variable Y(i)k (where k=1, 2, . . . , m) with n variables X(i−1)j (where j=1, 2, . . . , n). This association therefore consists in a particular function “G”, which associates with an n-tuple X=(x1, x2, . . . , xn) of input values the m-tuple Y=(y1, y2, . . . , ym) of output values. This function G therefore corresponds to a system (G) of m multivariate quadratic polynomials (i.e. with n variables x1 to xn, where n>1) over a finite body K. These polynomials are therefore of the following form, in which the coefficients belong to K and the quantities yk also belong to K:
                    ∑                  1          ≤          i          ≤          j          ≤          n                    ⁢                        α          k                      (            ij            )                          ⁢                  x          i                ⁢                  x          j                      +                  ∑                  1          ≤          j          ≤          n                    ⁢                        β          k                      (            j            )                          ⁢                  x          j                      +          γ      k        =            y      k        ⁡          (              1        ≤        k        ≤        m            )      
In the conventional way to implement this kind of generator, the values of these coefficients would be stored in a memory and the values of the m polynomials would be calculated on each iteration. It would therefore be necessary to store a total number of coefficients equal to m·N, where N is the number of terms of each polynomial. It is a simple matter to verify that, for a quadratic polynomial with n variables, this number N of terms is equal to
  N  =      1    +                            n          ⁡                      (                          n              +              1                        )                          2            .      
Moreover, for solving a system of m quadratic equations in n unknowns over K to be considered difficult, it is desirable for the values of m and n to be sufficiently large and for their orders of magnitude to be sufficiently close. Thus for high values of n, and for values of m of the same order of magnitude as the values of n, the number of coefficients to be stored is of the order of n3. For example, if n is approximately equal to 100, approximately one million coefficients must be stored.
As a result, conventional implementation of a pseudorandom generator according to French patent application 05 06041 requires far too many electronic gates for it to be possible to envisage incorporating it into a hardwired logic chip. It goes without saying that it is even less feasible to envisage inserting into a hardwired logic chip a pseudorandom generator using a system of multivariate polynomials some of which have a global degree higher than 2, although polynomials of higher degree would have the advantage of making the generator more secure, at the cost of a modest increase in calculation resources.